// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包环实现对循环列表的操作。
package ring

// 环是循环列表或环的一个元素。
// 戒指没有开始或结束；指向任何环元素
// 的指针用作整个环的引用。空环表示为零环指针。一个环的零值是一个单元素
// 带nil值的环。
// 
type Ring struct {
	next, prev *Ring
	Value      any // 供客户使用；未被该库触及
}

func (r *Ring) init() *Ring {
	r.next = r
	r.prev = r
	return r
}

// Next返回下一个环元素。r不能为空。
func (r *Ring) Next() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.next
}

// Prev返回上一个环元素。r不能为空。
func (r *Ring) Prev() *Ring {
	if r.next == nil {
		return r.init()
	}
	return r.prev
}

// Move在环中向后（n<0）或向前（n>=0）移动n%r.Len（）元素
// 并返回该环元素。r不能为空。
// 
func (r *Ring) Move(n int) *Ring {
	if r.next == nil {
		return r.init()
	}
	switch {
	case n < 0:
		for ; n < 0; n++ {
			r = r.prev
		}
	case n > 0:
		for ; n > 0; n-- {
			r = r.next
		}
	}
	return r
}

// New创建一个由n个元素组成的环。
func New(n int) *Ring {
	if n <= 0 {
		return nil
	}
	r := new(Ring)
	p := r
	for i := 1; i < n; i++ {
		p.next = &Ring{prev: p}
		p = p.next
	}
	p.next = r
	r.prev = p
	return r
}

// 链接将环r与环s连接起来，使r.Next（）
// 变成s并返回r.Next（）的原始值。
// r不能为空。
// 
// 如果r和s指向同一个环，则链接
// 它们将从环中删除r和s之间的元素。
// 删除的元素形成一个子环，结果是对该子环的引用（如果没有删除任何元素，
// 结果仍然是r.Next（）、
// 的原始值，而不是零）。
// 
// 如果r和s指向不同的环，链接
// 它们会创建一个环，其中s的元素插入
// 在r之后。结果指向
// 插入后s的最后一个元素。
// 
func (r *Ring) Link(s *Ring) *Ring {
	n := r.Next()
	if s != nil {
		p := s.Prev()
		// 注意：由于未指定LHS的求值顺序，因此无法使用多个赋值。
		r.next = s
		s.prev = r
		n.prev = p
		p.next = n
	}
	return n
}

// Unlink从环r中删除n%r.Len（）元素，从r.Next（）开始
// 。如果n%r.Len（）==0，则r保持不变。
// 结果是移除的子环。r不能为空。
// 
func (r *Ring) Unlink(n int) *Ring {
	if n <= 0 {
		return nil
	}
	return r.Link(r.Move(n + 1))
}

// Len计算环r中的元素数。
// 它的执行时间与元素数成比例。
// 
func (r *Ring) Len() int {
	n := 0
	if r != nil {
		n = 1
		for p := r.Next(); p != r; p = p.next {
			n++
		}
	}
	return n
}

// Do按正向顺序对环的每个元素调用函数f。
// 如果f改变，Do的行为是未定义的*r.
func (r *Ring) Do(f func(any)) {
	if r != nil {
		f(r.Value)
		for p := r.Next(); p != r; p = p.next {
			f(p.Value)
		}
	}
}
